package Dijkstra;

import java.util.*;

/**
 * Created by fengliejv on 2017/12/22.
 */
//todo 应该用dijkstra
public class NetworkDelayTime743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        //到某个点的距离列表
        int[] distance = new int[n + 1];
        for (int i = 0; i < distance.length; i++) {
            distance[i] = Integer.MAX_VALUE;
        }

        //记录每条路径是否访问过
        boolean[] visited = new boolean[times.length];
        for (int i = 0; i < visited.length; i++) {
            visited[i] = false;
        }

        //预处理每条路径
        Map<Integer, List<Integer>> routMap = new HashMap<>();
        for (int i = 0; i < times.length; i++) {
            List<Integer> list = routMap.getOrDefault(times[i][0], new ArrayList<>());
            list.add(i);
            routMap.put(times[i][0],list);
        }
        //广度优先的队列
        LinkedList<Integer> queue = new LinkedList<>();
        List<Integer> roots = routMap.get(k);
        for (int i = 0; i <roots.size() ; i++) {
            queue.add(roots.get(i));
        }

        distance[k] = 0;

        //广度优先遍历
        while (queue.size()!=0){
            Integer index = queue.pop();
            if(visited[index]){
                continue;
            }
            visited[index] = true;
            int[] route = times[index];
            int begin = route[0];
            int end = route[1];
            int time = route[2];
            distance[end] = Math.min(distance[end],distance[begin]+time);
            queue.addAll(routMap.get(end));
        }

        //处理结果
        int result = -1;
        for (int i = 1; i < distance.length; i++) {
            if (distance[i] == Integer.MAX_VALUE) {
                return -1;
            }
            result = Math.max(result, distance[i]);
        }
        return result;
    }

}
